import java.util.*;

public class Solution {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;

        if(root == p || root == q) return root;

        if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left, p, q);
        }else if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right, p, q);
        }else{
            //System.out.println(1);
            return root;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        //List<Integer> tmp = new ArrayList<>();
        if(root == null){
            return ans;
        }
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            int sz = queue.size();
            for(int i = 0; i < sz; i++){
                TreeNode cur = queue.remove();
                tmp.add(cur.val);
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            //for(Integer e : tmp)
            //System.out.println(e + " ");
            //System.out.println();
            ans.add(new ArrayList<>(tmp));
        }
        return ans;
    }

//    public static void main(String[] args) {
//        ArrayList<Integer> list = new ArrayList<>();
//        for(int i = 1; i <= 10; i++){
//            list.add(i);
//        }
//        ArrayList<Integer> list2 = new ArrayList<>(list);
//        list.set(1, 15);
//        for(Integer e : list){
//            System.out.print(e + " ");
//        }
//    }
}
